#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
const int MOD = 1e4+7;
bool sta[N];
int f[N][N];
int qpow(int x,int p){
    int res = 1;
    while(p)
    {
        if(p & 1){
            res = 1ll*res*x%MOD;
        }
        x = 1ll*x*x%MOD;
        p >>= 1;
    }
    return res;
}
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i = 1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        sta[u] ^= 1;
        sta[v] ^= 1;
    }
    int tot = 0;
    for(int i = 1;i<=n;i++){
        tot += sta[i];
    }
    //cerr<<tot<<'\n';
    int inv2 = (MOD + 1)/2;
    f[0][tot] = 1; 
    for(int j = 1;j <= k;j++){
        int dv = 1ll*(1ll*n*(n - 1)%MOD*inv2%MOD - (j - 2) + MOD)%MOD*(j - 1)%MOD;
        f[j][0] = (f[j - 1][2] - (j >= 2?1ll*f[j - 2][0]*dv%MOD:0) + MOD)%MOD;
        for(int v = 2;v <= n;v += 2){
            f[j][v] = (1ll*f[j - 1][v + 2]*(v + 2)%MOD*(v + 1)%MOD*inv2%MOD + 1ll*f[j - 1][v]*v%MOD*(n - v)%MOD + 1ll*f[j - 1][v - 2]*(n - (v - 2))%MOD*(n - (v - 2) - 1)%MOD*inv2%MOD)%MOD;
            f[j][v] = (f[j][v] + MOD - (j >= 2?1ll*f[j - 2][v]*dv%MOD:0))%MOD;
        }
    }
    int vl = 1;
    for(int i = 1;i<=k;i++){
        vl = 1ll*vl*i%MOD;
    }
    vl = qpow(vl,MOD - 2);
    cout<<1ll*f[k][0]*vl%MOD<<'\n';
}